package com.arron.algorithm.leetcodetop100.数组;

import java.util.Arrays;

public class 除自身以外数组的乘积 {



    // 题解  https://leetcode.cn/problems/product-of-array-except-self/solutions/11472/product-of-array-except-self-shang-san-jiao-xia-sa/?envType=study-plan-v2&envId=top-100-liked
    public int[] productExceptSelf(int[] nums) {

        int[] res = new int[nums.length];


        res[0] = 1;

        int temp =1;


        //计算左下角
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i-1]*nums[i-1];
        }


        for (int i = nums.length-2; i >=0 ; i--) {
            temp =temp*nums[i+1];
            res[i] = res[i] * temp;

        }

        return res;
    }



    /**
     *  暴力破解 时间O(n2)
     * @param nums
     * @return
     */
    public int[] productExceptSelf_down(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int k = 1;
            int j = i+1;
            while (j<nums.length){
                k = k*nums[j];
                j++;
            }
            j = i-1;
            while (j>=0){
                k = k*nums[j];
                j--;
            }
            res[i] = k;
        }
        return res;
    }


    public static void main(String[] args) {
        除自身以外数组的乘积 a = new 除自身以外数组的乘积();
        int[] nums = {1,2,3,4};
        int[] ints = a.productExceptSelf(nums);

        System.out.println(Arrays.toString(ints));
    }

}
